#include<iostream>




template<typename T>
class DoubleLinkList
{

public:
    DoubleLinkList();

    void InsertTail(const T&element);
    
    void InsertHead(const T&element);


    // 中间插入
    void InsertByIndex(int index,const T &element);

    
    // 按位置删
    void RemoveByIndex(int index);  

    // 按值删
    void RemoveElement(const T&element);

    // void* 回调用


    ~DoubleLinkList();

    void show();
    
    int Size()
    {
        return this->size;
    }

    T* Back()
    {
        return & tail->data;
    }

    T* Head()
    {
        return &head->next->data;
    }

private:
    struct Node
    {
        Node(const T &data):data(data),prev(nullptr),next(nullptr){}
        T data;
        Node*next;
        Node*prev;//前置指针

    };
    
    Node* head;//头指针
    Node* tail;//尾指针
    int size;
    
};



template<typename T>
DoubleLinkList<T>::DoubleLinkList():size(0)
{
    head = new Node(0);
    tail = head;
}

template<typename T>
void DoubleLinkList<T>::InsertTail(const T &element)
{
    Node* newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    
    this->size++;
}

template<typename T>
void DoubleLinkList<T>::InsertHead(const T &element)
{
    Node *newNode = new Node(element);
    
    newNode->next = head->next;
    newNode->prev = head;
    head->next = newNode;
    
    if(size !=0)
    newNode->next->prev = newNode;
    else
    {
        tail = newNode;
    }
    size++;
}

template<typename T>
void DoubleLinkList<T>::InsertByIndex(int index,const T &element) //中间插入
{
    Node* travelPoint = head; 
    for(int i=0;i < index;i++)
    {
        travelPoint = travelPoint->next;
    }
    
    Node* newNode = new Node(element); 
    
    newNode->next = travelPoint->next;
    newNode->prev = travelPoint;

    travelPoint->next = newNode;
    if(size != index)
    newNode->next->prev = newNode;
    else
    {
        tail = newNode;
    } 
    size++;




}


template<typename T>
void DoubleLinkList<T>::RemoveByIndex(int index)
{
    if(index<0 || index >= size)
    {
        std::cout<<"非法的删除位置\n";
        return;
    }

    Node* travelPoint = head;
    
    for(int i=0;i<index;i++)
    {
        travelPoint = travelPoint->next;
    }
    
    Node* freeNode = travelPoint->next;

    travelPoint->next = freeNode->next;
    
    if(size != index + 1)
    freeNode->next->prev = travelPoint;
    else
    {
        tail = travelPoint;
        travelPoint->next = nullptr;
    }  
    delete freeNode;
    size--;
}

template<typename T>
void DoubleLinkList<T>::RemoveElement(const T &element)
{
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
    {
        if(travelPoint->next->data == element)
        {
            Node* freeNode = travelPoint->next;
            
            travelPoint->next = freeNode->next;

            if(freeNode->next == nullptr)
                {
                    tail = travelPoint;
                }
            if(freeNode->prev == head)
                {
                    freeNode->next->prev =head;
                }
            delete freeNode;
            size--; 
        }
        else
        travelPoint = travelPoint->next;
    }
}



template<typename T>
DoubleLinkList<T>::~DoubleLinkList()
{
        while(head != nullptr)
    {
        Node* nextNode = head ->next;//记下下一个结点
        delete head;
        head = nextNode;// 结点往后走
    }
}
template<typename T>
void DoubleLinkList<T>::show()
{   
    Node *travelPoint = head->next;
    std::cout<<this->size<<std::endl;
    while (travelPoint != nullptr)
    {   
        std::cout<<travelPoint->data<<" ";
        travelPoint = travelPoint->next;
    }
    std::cout<<std::endl;

    travelPoint = tail;
    while(travelPoint != head)
    {
        std::cout<<travelPoint->data<<" ";
        travelPoint = travelPoint->prev; 
    }
    std::cout<<std::endl;
}
